package top.jafar.data.structures;

public class SparseArray {
    public static void main(String[] args) {

        new SparseArray();

    }

    public SparseArray() {
        // 定义原始数组
        int[][] chessArray = new int[11][11];
        // 随机插入棋子
        int chessCount = randInt(5)+3;
        for (int i = 0; i < chessCount; i++) {
            chessArray[randInt(10)][randInt(10)] = randInt(2);
        }
        // 打印+创建稀疏数组
        System.out.println("原始数组: ");
        printArray(chessArray);
        int[][] sparseArray = createSparseArray(chessArray);
        System.out.println("稀疏数组: ");
        printArray(sparseArray);
        int[][] fromSpaceArray = createFromSpaceArray(sparseArray);
        System.out.println("还原后的原始数组: ");
        printArray(fromSpaceArray);
    }

    /**
     * 从稀疏数组还原成原始数组
     * @param spaceArr
     * @return
     */
    public int[][] createFromSpaceArray(int[][] spaceArr) {
        int[][] targetArr = new int[spaceArr[0][0]][spaceArr[0][1]];
        for (int i = 1; i < spaceArr.length; i++) {
            targetArr[spaceArr[i][0]][spaceArr[i][1]] = spaceArr[i][2];
        }
        return targetArr;
    }

    /**
     * 创建稀疏数组
     * @param originArr
     * @return
     */
    public int[][] createSparseArray(int[][] originArr) {
        int totalCount = 0;
        for (int i = 0; i < originArr.length; i++) {
            for (int j = 0; j < originArr[i].length; j++) {
                if (originArr[i][j] != 0) {
                    totalCount ++;
                }
            }
        }
        int[][] sparseArray = new int[totalCount+1][3];
        sparseArray[0][0] = originArr.length;
        sparseArray[0][1] = originArr[0].length;
        sparseArray[0][2] = totalCount;
        int count = 0;
        for (int i = 0; i < originArr.length; i++) {
            for (int j = 0; j < originArr[i].length; j++) {
                if (originArr[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = originArr[i][j];
                }
            }
        }
        return sparseArray;
    }

    /**
     * 打印数组
     * @param arr
     */
    public void printArray(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            int[] chessArray1 = arr[i];
            for (int j = 0; j < chessArray1.length; j++) {
                System.out.printf("%d\t", chessArray1[j]);
            }
            System.out.println();
        }
    }

    public int randInt(int max) {
        return (int)(Math.random()*max)+1;
    }
}
